'''
https://leetcode.cn/problems/search-a-2d-matrix/?envType=study-plan-v2&envId=top-interview-150
'''
import bisect
from typing import List


class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        def idx1D(i, j):
            return i * n + j
        def idx2D(i):
            return i // n, i % n
        l, r = 0, m * n - 1
        while l <= r:
            mid = l + r >> 1
            i, j = idx2D(mid)
            if matrix[i][j] == target:
                return True
            elif matrix[i][j] < target:
                l = mid + 1
            else:
                r = mid - 1
        return False

matrix = [[1, 3]]
target = 3
print(Solution().searchMatrix(matrix, target))

